package core;

import fileoperation.FileReader;

import java.io.FileNotFoundException;
import java.util.ArrayList;

public class JitDiff {
    /**
     * Compare difference between files.
     * @param f1, f2
     * @throws FileNotFoundException
     */
    public static void compareFiles(String f1, String f2) throws FileNotFoundException {
        ArrayList<String> f1Lines = FileReader.readFromFile(f1); // get list of lines
        ArrayList<String> f2Lines = FileReader.readFromFile(f2);

        ArrayList<Integer> steps = getShortest(f1Lines, f2Lines); // get the shortest path in reverse order

        printDiff(steps, f1Lines, f2Lines); // print difference
    }

    /**
     * Print difference between files based on the shortest path found.
     * @param steps, f1Lines, f2Lines
     */
    private static void printDiff(ArrayList<Integer> steps, ArrayList<String> f1Lines, ArrayList<String> f2Lines) {
        int m=0, n=0;
        for (int i=steps.size()-1; i>=0; i--) {
            if (steps.get(i) == 1) { // deletion
                System.out.println("- " + f1Lines.get(m));
                m++;
            }
            else if (steps.get(i) == -1) { // insertion
                System.out.println("+ " + f2Lines.get(n));
                n++;
            }
            else {
                System.out.println("  " + f1Lines.get(m));
                m++;
                n++;
            }
        }
    }

    /**
     * Calculate the shortest path.
     * @param f1Lines, f2Lines
     * @return ArrayList<Integer>
     */
    private static ArrayList<Integer> getShortest(ArrayList<String> f1Lines, ArrayList<String> f2Lines) {
        int m = f1Lines.size();
        int n = f2Lines.size();

        int[][] array = new int[n+1][m+1];

        // initialization
        for (int i=0; i<=m; i++) {
            array[0][i] = i;
        }
        for (int j=0; j<=n; j++) {
            array[j][0] = j;
        }
        // calculate steps needed for each position
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=m; j++) {
                if (f1Lines.get(j-1).equals(f2Lines.get(i-1))) {
                    array[i][j] = array[i-1][j-1];
                }
                else {
                    int minVal = 1 + Math.min(array[i-1][j], array[i][j-1]);
                    array[i][j] = minVal;
                }
            }
        }
        // backtrack 2d-array to find path
        ArrayList<Integer> path = new ArrayList<>();
        int p=n, q=m;
        while (p!=0 && q!=0) {
            if (array[p-1][q] == array[p][q-1]) {
                if (array[p-1][q] == array[p][q]-1) {
                    path.add(-1); // insertion
                    p--;
                }
                else {
                    path.add(0);
                    p--;
                    q--;
                }
            }
            else if (array[p-1][q] < array[p][q-1]) {
                path.add(-1); // insertion
                p--;
            }
            else {
                path.add(1); // deletion
                q--;
            }
        }
        while (p!=0) {
            path.add(-1);
            p--;
        }
        while (q!=0) {
            path.add(1);
            q--;
        }

        return path;
    }
}
